package 链表;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 重排链表
 * 给定一个单链表 L 的头节点 head ，单链表 L 表示为：L0 → L1 → … → Ln - 1 → Ln
 * 请将其重新排列后变为：L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
 * 输入：head = [1,2,3,4]
 * 输出：[1,4,2,3]
 * @author 翟晓龙
 * @date 2022/4/1
 */
public class 重排链表 {

    /**
     * 初始化链表
     * @return
     */
    public static Node initData(){
        Node node1 = new Node();
        node1.value = 1;
        Node node2 = new Node();
        node2.value = 2;
        Node node3 = new Node();
        node3.value = 3;
        Node node4 = new Node();
        node4.value = 4;

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        return node1;
    }

    public static void main(String[] args) {
        Node linked = initData();
        Node newLinked = updateLinked2(linked);
        System.out.println(newLinked);
    }

    public static Node updateLinked2(Node head) {
        List<Node> nodeList = new ArrayList<>();
        while (head != null) {
            nodeList.add(head);
            head = head.next;
        }
        Node newHead = new Node();
        Node curr = newHead;
        int i = 0, j = nodeList.size() - 1;
        while (i <= j) {
            Node node_i = nodeList.get(i);
            node_i.next = null;
            curr.next = node_i;
            curr = curr.next;
            if (i != j) {
                Node node_j = nodeList.get(j);
                node_j.next = null;
                curr.next = node_j;
                curr = curr.next;
            }
            i++;
            j--;
        }
        return newHead.next;
    }


    /**
     * 重排
     * @param head
     * @return
     */
    public static Node updateLinked(Node head){
        List<Node> values = new LinkedList<>();
        Node node = head;
        while (head != null){
            values.add(head);
            head = head.next;
        }
        int i = 0;
        int j = values.size() - 1;
        while (i < j){
            values.get(i).next = values.get(j);
            if (i == j){
                break;
            }
            i ++;
            values.get(j).next = values.get(i);
            j --;
        }
        values.get(i).next = null;
        return node;
    }
}
